// 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

// candidates 中的数字可以无限制重复被选取。

// 说明：

// 所有数字（包括 target）都是正整数。
// 解集不能包含重复的组合

var combinationSum = function(candidates, target) {
    let cal = candidates.sort((a, b) => { return a - b; });
    let sum = new Array();
    for (let i = 0; i < cal.length; i++) {
        let lin = parseInt(target / cal[i]);
        for (let j = 1; j < lin; j++) {
            let tar = target - a[i] * j;
            for (k = i; k < cal.length; k++) {

            }
        }
    }
};
// 思路：根据一个数的N倍与和的大小关系遍历每一种可能的重复组合

const combinationSum = (candidates, target) => {
    const res = [];
    const dfs = (start, temp, sum) => { // start是当前选择的起点索引 temp是当前的集合 sum是当前求和
        if (sum >= target) {
            if (sum == target) {
                res.push(temp.slice()); // temp的拷贝 加入解集
            }
            return; // 结束当前递归
        }
        for (let i = start; i < candidates.length; i++) { // 枚举当前可选的数，从start开始
            temp.push(candidates[i]); // 选这个数
            dfs(i, temp, sum + candidates[i]); // 基于此继续选择，传i，下一次就不会选到i左边的数
            temp.pop(); // 撤销选择，回到选择candidates[i]之前的状态，继续尝试选同层右边的数
        }
    };
    dfs(0, [], 0); // 最开始可选的数是从第0项开始的，传入一个空集合，sum也为0
    return res;
};